package com.str.map;
public class ArrayMap implements Map {

  // Each ArrayMap object is a bounded map in which the keys are
  // Comparable objects and the values are arbitrary objects.

  // This map is represented as follows: its cardinality is held in card;
  // its entries (which are sorted by key) occupy the subarray entries
  // [0...card-1].

// Inner class
  private static class Entry {
    // Each ArrayMap.Entry object is a map entry consisting of a key,
    // which is a Comparable object, and a value, which is an arbitrary
    // object.
    Object key;
    Object value;

    Entry(Object k, Object v) {
      key = k;
      value = v;
    }
    	
    public String toString()
    { return "<" + key + "," + value + ">";	}
  }

  private final int DEFAULT_SIZE = 10;
  private Entry[] array;
  private int count;

// Constructor
  public ArrayMap() {
  // Construct a map, initially empty, whose cardinality will be bounded by
  // maxcard.
    array = new Entry[DEFAULT_SIZE];
    count = 0;
  }

// Modifiers
  public void clear() {
  // Make this map empty.
    for (int i = 0; i < count; i++)
      array[i] = null;
    count = 0;
  }

  public void add(Object key, Object val) {
  // Add the entry <key, val> to this map, replacing any existing entry with
  // key. Return the value in that entry, or null if there was no such entry.
    int pos = search(key);
    if (pos < 0) {
      if (count == array.length) expand();
      array[count++] = new Entry(key, val);
    }
  }

  public Object remove(Object key) {
    // Remove the entry with key (if any) from this map. Return the value
    // in that entry, or null if there was no such entry.
    int pos = search(key);
    if (pos < 0) return null; 
    Object temp = array[pos];
    array[pos] = array[count - 1];
    array[--count] = null;
    return temp;
  }

// Accessors  
  public boolean isEmpty() {
  // Return true if and only if this map is empty.
	return count == 0;
  }

  public int size() {
    // Return this map's size.
	return count;
  }
    
  public Object getValue(Object key) {
    // Return the value in the entry with key in this map, or null if there
    // is no such entry.
    int pos = search(key);
    if (pos < 0) return null;
    return array[pos].value;     
  }

// Auxiliary methods
  private int search(Object key) {
    for (int i = 0; i < count; i++)
      if (key.equals(array[i].key))
        return i;
    return -1;
  }
  
  private void expand() {
  	Entry[] newArray = new Entry[2 * array.length];
  	for (int i = 0; i < array.length; i++)
  	  newArray[i] = array[i];
  	array = newArray;
  }      

  public String toString() {
    String buf = "{ ";
    for (int i = 0; i < count; i++) {
      if (i > 0)  buf += ", ";
      buf += array[i];
    }
    buf += " }";
    return buf;
  }
}
